package middle;


/**
 * 给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
 * 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 *
 * 不允许修改 链表。
 *
 * 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
 *
 * */
public class LinkedListCycleII {
    /**
     * 快慢指针法。
     * 我们定义两个指针slow 和 fast
     * slow每次走一个结点，fast每次走两个结点
     * 由此我们可以知道fast走过的结点数 f = 2s
     * 已知一个环形链表的组成是 直线部分 和 环部分。我们假设直线部分结点数为a，环部分的结点数为b
     * 当fast指针与slow在环中相遇时，fast比slow多走x圈。即f  = s + xb
     * s + xb = 2s
     * s = xb
     * 此时可以得知，Slow指针已经走过了x个圈，如果我们再走a个结点就可以到达环的入口 即Slow走了(a + xb)
     * */
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while(true){
                if(fast == null || fast.next == null) return null;
                slow = slow.next;
                fast = fast.next.next;
                if(fast == slow) break;
            }

            fast = head;
            while (fast != slow){
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
    }
}
